package main

import "fmt"

func main() {
	arr := []int{64, 25, 12, 22, 11}
	fmt.Println("原始数组:", arr)
	sortedArr := quickSort(arr)
	fmt.Println("排序后数组:", sortedArr)
}

/**
快速排序（Quick Sort）是一种高效的排序算法，
它是一种分治算法，通过递归的方式将数据依次分解为较小的数据子集，
以达到排序的目的。快速排序的基本思想是选择一个基准元素（pivot），
然后将数组分成两个部分，将小于基准元素的值放到基准的左边，将大于或等于基准元素的值放到基准的右边。
这个过程称为分区（partitioning）。然后递归地对基准左侧和右侧的子数组进行快速排序。
*/
// quickSort 对整数切片进行快速排序
func quickSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	pivot := arr[0] // 选择第一个元素作为基准
	left := make([]int, 0)
	right := make([]int, 0)
	middle := make([]int, 0)

	for _, val := range arr {
		switch {
		case val < pivot:
			left = append(left, val)
		case val == pivot:
			middle = append(middle, val)
		case val > pivot:
			right = append(right, val)
		}
	}

	// 递归地对左侧和右侧的子切片进行快速排序
	return append(append(quickSort(left), middle...), quickSort(right)...)
}
